package algorithms.leaning.class12;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * 给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离
 *
 * @author guichang
 * @date 2021/6/12
 */

@SuppressWarnings("all")
public class Code4_二叉树_最大距离 {
    // 1、不经过头节点，左树最大距离或右树最大距离为结果
    // 2、经过头节点，最大距离=左树高度+右树高度+1
    // 3、三者求max

    public static void main(String[] args) {
//        TreeNode head = MyUtil.createTreeNode(1, 2, 3, 4, 5, null, null, 6, null, null, 7, 8, null, null, 9); // 7
        TreeNode head = MyUtil.createTreeNode(1, 2, 3, 4, null, null, 5); // 5
        MyUtil.print(maxDis(head));
    }

    public static int maxDis(TreeNode head) {
        return process(head).maxDis;
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return new Info(0, 0);
        }
        Info tl = process(node.left);
        Info tr = process(node.right);
        int height = Math.max(tl.height, tr.height) + 1;
        int maxDis = Math.max(Math.max(tl.maxDis, tr.maxDis), tl.height + tr.height + 1);
        return new Info(maxDis, height);
    }

    private static class Info {
        int maxDis;
        int height;

        public Info(int maxDis, int height) {
            this.maxDis = maxDis;
            this.height = height;
        }
    }
}